package com.wdc.回溯;

import java.util.ArrayList;
import java.util.List;

@SuppressWarnings("all")
public class E07Leetcode93 {

    /**
     * 错误代码
     */
//    private List<test> result = new ArrayList<>();
//    public List<test> restoreIpAddresses(test s) {
//        backtracking(s,0);
//        return result;
//
//    }
//    StringBuilder temp = new StringBuilder();
//    //点的数量
//    int poinNum = 0;
//    void backtracking(test s, int startIndex){
//        //结束条件
//        if (startIndex >= s.length()){
//            result.add(temp.toString());
//        }
//        if (poinNum == 3){
//            return;
//        }
//        //横向遍历
//        for (int i = startIndex; i < s.length(); i++) {
//            test str = s.substring(startIndex, i + 1);
//            if (isIPNum(str)) {
//                temp.append(str);
//                temp.append(".");
//                poinNum++;
//            }
//            //递归求深度
//            backtracking(s,i + 1);
//            //回溯
//            temp.deleteCharAt(temp.length()-1);
//
//        }
//
//
//    }
//
//    boolean isIPNum(test str){
//        Integer num = Integer.valueOf(str);
//        if (num >= 0 && num <= 255){
//            return true;
//        }
//        return false;
//    }
//

    private List<String> result = new ArrayList<>();
    public List<String> restoreIpAddresses(String s) {
        StringBuilder sb = new StringBuilder(s);
        backtracking(sb, 0, 0);
        return result;

    }
    void backtracking(StringBuilder s, int startIndex,int pointNum){
        //结束递归条件
        if (pointNum == 3){
            //判断是否是有效IP
            if (isIPNum(s,startIndex,s.length() -1)){
                result.add(s.toString());
            }
            return;
        }

        for (int i = startIndex; i < s.length(); i++) {
            if (isIPNum(s,startIndex,i)){
                s.insert(i +1 ,'.');
                backtracking(s,i + 2,pointNum +1);
                s.deleteCharAt(i + 1);
            }else {
                break;
            }
        }


    }

    boolean isIPNum(StringBuilder s, int start , int end){
        if (start > end){
            return false;
        }
        if (s.charAt(start) == '0' && start != end){
            return false;
        }
        int num = 0;
        for (int i = start; i <= end; i++) {
            int digit = s.charAt(i) - '0';
            num = num * 10 + digit;
            if (num > 255){
                return false;
            }
        }
        return true;

    }




}
